#include <stdio.h>
#include <stdlib.h>
#define random(x) (rand()%x)
#define MAXN 64
void swap(int* a, int* b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void Insertsort2(int* put, int size)
{
	int j, p;
	int tmp;
	for (p = 1; p < size; p++)
	{
		tmp = put[p];
		for (j = p; j > 0 && put[j - 1] > tmp; j--)
			put[j] = put[j - 1];
		put[j] = tmp;
	}
}
int median3(int* putin, int left, int right)
{
	int center = (left + right) / 2;
	if (putin[left] > putin[center])
		swap(&putin[left], &putin[center]);
	if (putin[left] > putin[right])
		swap(&putin[left], &putin[right]);
	if (putin[center] > putin[right])
		swap(&putin[center], &putin[right]);
	swap(&putin[center], &putin[right - 1]);
	return putin[right - 1];
}
void q_sort(int* qputin, int left, int right)
{
	int i, j, pivot, cutoff = 7;
	if (left + cutoff <= right)
	{
		pivot = median3(qputin, left, right);
		i = left; j = right - 1;
		for (;;)
		{
			while (qputin[++i] < pivot) {}
			while (qputin[--j] > pivot) {}
			if (i < j)
				swap(&qputin[i], &qputin[j]);
			else
				break;
		}
		swap(&qputin[i], &qputin[right - 1]);
		q_sort(qputin, left, i - 1);
		q_sort(qputin, i + 1, right);
	}
	else
	{
		Insertsort2(qputin + left, right - left + 1);
	}
}
void QuickSort(int* putin, int size)
{
	q_sort(putin, 0, size - 1);
}
int main() {
	int* array_test = (int*)malloc(sizeof(int) * MAXN);
	puts("The original array: ");
	for (int i = 0; i < MAXN; i++) {
		array_test[i] = random(100);
		printf("%d ", array_test[i]);
		if ((i + 1) % 16 == 0)printf("\n");
	}
	QuickSort(array_test, MAXN);
	puts("After sorted: ");
	for (int i = 0; i < MAXN; i++) {
		printf("%d ", array_test[i]);
		if ((i + 1) % 16 == 0)printf("\n");
	}
}